// SortThread.java

package com.ibm.tspaces.examples.mergesort;

import	java.util.Vector;
import  com.ibm.tspaces.examples.mergesort.VectorWithEquals;
import	com.ibm.tspaces.*;

/*
**  Licensed Materials - Property of IBM
**
**  (C) COPYRIGHT IBM Corp. 1997  All rights reserved
**
**  US Government Users Restricted Rights - Use, duplication or
**  disclosure restricted by GSA ADP Schedule Contract with IBM Corp.
**
**/

/**
** This class implements a merge sort using a TupleSpace to hold
** the values to be sorted and intermediate results.
**
** @see MergeSort
** @see Tuple
** @see Field
** @see TupleSpace
** @version $Revision: 2.1.2.2 $ $Date: 2000/08/30 12:54:18 $
** @author Daniel Ford
*/

public class SortThread extends Thread {

  /*
  ***************************************************************************
  ** ** Members **
  ** *************
  **
  */

  /**
  **	The TupleSpace used to hold values.
  */
  private TupleSpace	ts	= null;

	
  /**
  **	The index of this thread.
  */
  private int		i 	= -1;

  
  /** 
  ** Count of Tuple reads.
  */
  public int  t1cnt = 0;
  public int  t2cnt = 0;
  
  
  /*
  ***************************************************************************
  ** ** SortThread **
  ** ****************
  */
  /**
  ** Create a SortThread.
  ** @param ts the TupleSpace where the values to be sorted are stored.
  ** @param i the index of the thread.
  ** @see TupleSpace
  ***************************************************************************
  */
  public SortThread( TupleSpace ts, int i ) {
    super("SortThread-"+i);
    this.ts	=	ts;
    this.i	=	i;
  	
  } // SortThread

  /*
  ***************************************************************************
  ** ** run **
  ** *********
  */
  /**
  ** The starting point of execution.
  ***************************************************************************
  */
  public void run()
  {
    pause(5);  // let the space get initialized.
    Debug.out(0," starting" );
    
    try {
      // Make a tuple to be used as a template for retrieving tuples with
      // Vectors of integers to be merge sorted.
      DataTuple	formalDataTuple	=	new DataTuple();
      
      // Make a tuple to be used to as a tempalte for retrieving tuples
      // the count of the number of integers to sort.  This is used
      // to tell us when we are done sorting.
      CountTuple formalCountTuple = new CountTuple();
      
      // Loop forever
      while ( true ) {
 
        // Try to get a Vector of integers to be sorted from the TupleSpace
        // 
        //DataTuple  t1  =  (DataTuple)ts.waitToTake( formalDataTuple, 60*1000 );
        DataTuple  t1  =  (DataTuple)ts.waitToTake( formalDataTuple );
        if ( t1 == null) {
            Debug.out(0,"Timeout from waitToTake while getting T1");
            Debug.out(0,"This should not happen. ");
            System.exit(1);
          }
    
        t1cnt++;
         // Got one Vector, try to get another so we can merge them.
        Debug.out(  " t1 = " + t1.toString() );
      
        DataTuple t2  =  (DataTuple)ts.take( formalDataTuple );
        
        if ( t2 != null) {
          t2cnt++;
          Debug.out(  " t2 = " + t2.toString() );
          DataTuple out =  mergeTuples( t1, t2 );
          
          TupleID tid = ts.write(out );
          Debug.out(" out = " + tid+" "+out.toString());
        } else { // else didn't get second Vector
              // No
              // Didn't get the second vector.  This could be because there is
              // only one vector tuple in the space.  If this is the case then
              // we want to signal that the sorting is complete.  We do that by
              // getting the count of the number of integers to sort, if that
              // value equals the size of the Vector of integers then we are done.
              // If the value doesn't equal it then some other thread has another
              // vector.  The one that grabs the count first is the one responsible
              // for finishing off.  So if we didn't grab the count, we return the
              // the Vector, if we did get the count, then we wait for a second
              // vector to show up.
      
            Debug.out(  " t2 = null, trying for the count" );
      
            CountTuple countTuple = (CountTuple)ts.take( formalCountTuple );
                // Did we get the count?
           if( countTuple != null ) {              
              // Yes
               //Debug.setDebugOn(true); //?????
               //TupleSpace.setDebug(true);   // ????????
               //ts.status(ts.getServer());  // status patched to turn on debug at server
              Debug.out(  " got count = " + countTuple.toString() );
              Debug.out(  " t1 = "+t1);
              int count  = countTuple.getCount();
              // we are now going to finish the sort in this thread
              while (true)  {
                VectorWithEquals vec  =  (VectorWithEquals)t1.getField(1).getValue();
                Debug.out(  " checking vector size " );
                boolean ok = checkVector(t1,count);
                // Is the count equal to the size of the Vector?
                if ( ok ) {
                  // Yes This means we're done.
                        Debug.out(  " we're done " );
      
                  ts.write( new DoneTuple( vec ));
                  break;
                  // end if count == vecSize
                } else  {  // current vector is not complete or out of order
                  if ( count > vec.size()) {
                    
                    // We're not done, but we have the count so somebody
                    // else should be returning a "data" tuple to the
                    // space, we'll wait for it.
                    Debug.out(0,  " size (" + vec.size() + " != " + 
                    count +") NOT equal. Wait for other datatuple " );
                
               
                    //t2 = (DataTuple)ts.waitToTake( formalDataTuple, 30*1000 );
                    t2 = (DataTuple)ts.waitToTake( formalDataTuple );
                    if ( t2 == null) {
                      Debug.out(0,"Timeout from waitToTake while holding count");
                      Debug.out(0,"This should not happen.");
                      
                      Debug.out(0,"v="+vec.dump());
                      //System.exit(1);
                    } else  {
                      Debug.out( " t2 = " + t2.toString() );
                      // Merge the vectors and return the count.
                      t1 =  mergeTuples( t1, t2 );
                      Debug.out(" t1 = " + t1.toString());
                    }
                  } else  { 
                    // this is an error condition.
                    Debug.out(0,  " size (" + vec.size() + " > " + count +"). Something went wrong." );
                    System.exit(1);
                  }
                } // not complete
              } // while true
            
             } else {  // could not get count
                Debug.out( " didn't get count, returning t1, exiting ..." );
      
                // No
                // We didn't get the count so return the first Vector.
              
                TupleID tid = ts.write( t1 );
                Debug.out(" t1 out = "+tid+" "+t1.toString());
                // We will let the guy that got the count do the rest of the 
                // sorting. 
                return;
      
             } // else didn't get the count
        } // else
      
      } // while True
	
    } // try
    catch ( TupleSpaceException tse ) {
      Debug.out(0,tse.getMessage());
      Debug.out(tse );
      
    } // catch

  } // run


  /*
  ***************************************************************************
  ** ** mergeTuples **
  ** *****************
  */
  /**
  ** Extract the two Vectors of integers from some data Tuples and merge sort
  ** them to produce a data Tuple with the values sorted.
  ** 
  ** @param t1 A Tuple with the second field a Vector of sorted integers.
  ** @param t2 A Tuple with the second field a Vector of sorted integers.
  ** @return A DataTuple that contains the sorted collection of the two 
  **           vectors extracted from the parameter Tuples.
  ** @exception TupleSpaceException if the format of the tuple is incorrect.
  ***************************************************************************
  */
  public DataTuple mergeTuples( DataTuple t1, DataTuple t2 ) throws TupleSpaceException {

	  return new DataTuple( mergeVectors( t1, t2 ));

  } // mergeTuples

  /*
  ***************************************************************************
  ** ** mergeVectors **
  ** *****************
  */
  /**
  ** Merge sort two vectors of sorted integers.
  ** 
  ** @param v1 A Vector of integers in increasing sorted order.
  ** @param v2 A Vector of integers in increasing sorted order.
  ** @return A Vector of the integers merge sorted.
  ***************************************************************************
  */
  public VectorWithEquals mergeVectors(DataTuple t1, DataTuple t2  ) 
             throws TupleSpaceException {
    Vector v1 = t1.getIntegers();
    Vector v2 = t2.getIntegers();
	  int	v1Size	=	v1.size();
	  int	v2Size	=	v2.size();
	  int	cur1	=	0;
	  int	cur2	=	0;

	  VectorWithEquals	sorted	=	new VectorWithEquals( v1Size + v2Size );

	  int	limit	=	v1Size + v2Size;

	  for ( int i = 0; i < limit; i++ ) {
		  // Have we finished the first vector?
		  if ( cur1 < v1Size ) {
			  // No
			  // Have we finished the second vector?
			  if ( cur2 < v2Size ) {
				  // No
				  // Okay, find the integer with the smallest
				  // value and put it into the sorted vector
				  // Is v1 < v2?
          int e1 = ((Integer)v1.elementAt( cur1 )).intValue();
          int e2 = ((Integer)v2.elementAt( cur2 )).intValue();
				  if ( e1 < e2 ) {					  
					  sorted.addElement( v1.elementAt( cur1++ ) );
				  }  else if (e1 > e2 ){					  
					  sorted.addElement( v2.elementAt( cur2++ ) );
				  } else  { // else v1 = v2  which is an error in our case
            Debug.out(0,"Duplicate element. "+e1);
            Debug.out(0,"v1 = "+((VectorWithEquals)v1).dump());
            Debug.out(0,"v2 = "+((VectorWithEquals)v2).dump());
            System.exit(1); 
				  } 
			  } // if finished second
			  else {
				  // Yes
				  // Finished the second Vector, just tag on the first
				  for ( ; cur1 < v1Size; cur1++ ) {
					  sorted.addElement( v1.elementAt( cur1 ) );
				  } // for
				  i = limit;
			  } // else finished second

		  } // if finished first
		  else {
			  // Yes
			  // Finished the first Vector, just tag on the second.
			  for ( ; cur2 < v2Size; cur2++ ) {
				  sorted.addElement( v2.elementAt( cur2 ) );
			  } // for
			  i = limit;
		  } 
	  } // for

	  return sorted;

  } // mergeVectors

/*
  ***************************************************************************
  ** ** checkVector **
  ** *****************
  */
  /**
  ** check what is missing from vector.
  ** 
  ** @param v1 A Vector of integers in increasing sorted order.  
  ** @return boolean
  ***************************************************************************
  */
  public boolean checkVector(DataTuple t1 , int count ) 
             throws TupleSpaceException {
    Vector v1 = t1.getIntegers();
   
	  int	v1Size	=	v1.size();
	  
	  int	position	=	0;
	  int current = 0;

	  Vector	missing	=	new Vector( v1Size  );	  

	  for ( int i = 0; i < count; i++ ) {
      if (position < v1Size)  {
		    current = ((Integer)v1.elementAt( position )).intValue();
      } else  {
        current = count;
      }
		  while (i < current) {
			  missing.addElement(new Integer(i));
        i++; 
		  }
      position++;      
	  }
		
    if (missing.size() >0) 	 {	
      Debug.out(0,"size: " + v1Size + ":" +count);	
      Debug.out(0,"Missing="+missing);
      return false;
    } else  {
      return true;
    }
               
	  

  } // checkVector

  /*
  ***************************************************************************
  ** ** puase **
  ** ***********
  */ 
  /**
  ** Suspend the thread for the indicated number of seconds.  This is useful
  ** for giving a user enough time to read a message displayed on the 
  ** console before the server goes down
  **
  ** @param seconds the number of seconds to pause
  **************************************************************************
  */
  private static void pause( int seconds ) {
    try {
		  Thread.sleep( seconds * 1000 );
    } // try
    catch( InterruptedException ie ) {}

  } // pause

  /*
  ***************************************************************************
  ** ** Main **
  ** **********
  */
  /**
  ** The starting point of execution for the sort thread
  ***************************************************************************
  */
  public static void main( String argv[] ) {

    try {
      String tsName		=	"mergesort";
      String tsServerName	=	"localhost";
      int numInts;
      // standard processing of operands
      if ( argv.length == 0) 
        System.out.println("Usage:  Mergesort [-D] [-h tsHost] count");
      for (int i=0; i< argv.length; i++) {
        if (argv[i].equals("-D") )
          Debug.setDebugOn(true);
        else if (argv[i].equals("-h")) {
          tsServerName = argv[++i];        
        } else         
          // if numeric than count
          try {
            numInts = Integer.parseInt( argv[i] );        
  
          } // try
          catch( NumberFormatException nfe ) {
            // Must be a host name
            tsServerName = argv[i];          
    
          } // catch
      }

     
	
      TupleSpace ts	=	new TupleSpace( tsName, tsServerName );
      
    	//if (Debug.isDebugOn()) 
      //	 	ts.setDebug(true);
      
      // assume that it is not allready done.
      ts.delete(new DoneTuple());
      SortThread sortThread =	new SortThread( ts, 0 );

      sortThread.start();
      DoneTuple done = (DoneTuple)ts.waitToRead(new DoneTuple());
      
      Debug.out("done="+done);
      System.out.println("Done: T1="+sortThread.t1cnt+" T2="+sortThread.t2cnt);

      //pause(10);
      ts.cleanup();
      System.exit(0);
    } // try
    catch( Exception e ) {
      Debug.out( "Exception: " + e.getMessage() );

    } // catch
    catch( Error err ) {
      Debug.out( "Error: " + err.getMessage() );

    } // catch
	
  } // main

} // SortThread
/* $Log: SortThread.java,v $
/* Revision 2.1.2.2  2000/08/30 12:54:18  jthomas
/* minor improvements to testcase
/*
/* Revision 2.4  2000/08/07 13:51:24  jthomas
/* changed to help find locking bug
/*
/* Revision 2.3  2000/07/28 15:16:25  jthomas
/* Improve testcase so itrecognizes error conditions
/* and terminates with an error message
/*
/* Revision 2.2  2000/07/07 15:46:20  jthomas
/* Use sleep instead of yield.
/*
/* Revision 2.1  1999/11/05 22:22:39  estesp
/* Update revision number to 2.1 on all files
/*
/* Revision 1.1.1.1  1999/11/05 16:24:53  estesp
/* Imported 2.1.0 release into Austin CVS
/*
 * Revision 1.3  1999/10/08 02:13:33  jthomas
 * minor debug output change
 *
 * Revision 1.2  1999/06/17 05:39:40  thodes
 *   Updated the inital checkin to append the "Log" field and
 * convert CR/LF to CR (for win/unix interop).
 *
 *   The inital checkin lower-cased directrory names, and omitted
 * many dirs/files that will added later, e.g., MoDAL stuff.
 *
 * All of the above will need to be done to all VSS-to-CVS
 * converted sources.  In summary, in moving from VSS to CVS, do this:
 *  - lower-case dir names
 *  - CR/LF --> CR
 *  - append CVS "Log" entties
 *
 * (a script that helps with #2 and #3 is in
 *     tspaces1:~thodes/bin/update-keywords.sh)
 * 
 */

